home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / pc / WD_SRC.ZIP / BSP_GEN / BSP_GEN.CPP next >
Encoding:
C/C++ Source or Header  |  1995-01-12  |  17.4 KB  |  646 lines
  1. #include "..\Source\LastWolf.hpp"                                                                  
  2.  
  3. // ERASE THIS.
  4. Fixed hello;
  5.  
  6.  
  7.  
  8. // The list of Lines and Points.
  9. CLineArray  *pLines;
  10. CPointArray *pPoints;                             
  11.  
  12. WORD nOriginalPoints, nOriginalLines;
  13.  
  14. // Global variable .. tells how many Lines were split.
  15. DWORD nSplits=0;
  16.  
  17. // How many times it's chosen the most balanced Line over the least splits.
  18. DWORD nBalancesChosen=1, nSplitsChosen=1;
  19.  
  20. // The percentage the program should try to maintain for choosing balance over splits.
  21. DWORD balanceImportance;
  22.  
  23. // How many times a line was split exactly along another line.
  24. WORD nExactIntersections=0;
  25.  
  26. // Used for best split calculations .. incremented each time the tree is split.
  27. WORD nSplitTrees=0;
  28.  
  29. // Makes BestSplit() use the best balance a certain amount of times..  Helps
  30. // to ensure that the top levels of the tree are as balanced as possible.
  31. WORD forceBalance=5;
  32.  
  33.  
  34. CLine *GenerateBspTree(BspCommandLine *pCommandLine, CLineArray *pLinesToFill, CPointArray *pPointsToFill)
  35. {
  36.     CLine *pRootNode;
  37.     WORD i;
  38.     
  39.     pLines = pLinesToFill;
  40.     pPoints = pPointsToFill;
  41.     
  42.     
  43.     dr_InitTables();
  44.     
  45.     if( pCommandLine->bDoomLevel )
  46.         printf("\nLoading WAD file %s..\n", pCommandLine->pFilename);
  47.     else
  48.         printf("\nLoading text file %s..\n", pCommandLine->pFilename);
  49.  
  50.     
  51.     if( pCommandLine->bDoomLevel )
  52.     {
  53.         if( !LoadDoomLevel( pCommandLine->pFilename, pCommandLine->pLevelName, pLines, pPoints, pCommandLine->bLoadDoomTextures, pCommandLine->pTextureWadName ) )
  54.         {
  55.             printf("Error loading WAD %s, level %d.\n\n", pCommandLine->pFilename, pCommandLine->pLevelName );
  56.             return NULL;
  57.         }
  58.     }   
  59.     else
  60.     {
  61.         if( !LoadTextData( pCommandLine->pFilename, pLines, pPoints) )
  62.         {
  63.             printf("\nCouldn't load the data!");
  64.             return NULL;
  65.         }
  66.     }
  67.  
  68.     
  69.     puts("");
  70.     puts("Creating BSP tree...");    
  71.  
  72.     balanceImportance = FIX(pCommandLine->balance) / 100;
  73.     
  74.     nOriginalPoints = pPoints->NumElements();
  75.     nOriginalLines = pLines->NumElements();
  76.     
  77.     // Just give all the Lines random wall colors.
  78.     for( i=0; i < pLines->NumElements(); i++ )
  79.         pLines->GetLine(i)->wallColor = rand() % 255;
  80.  
  81.     // Generate the tree.  After this function call, pLeft and pRight should
  82.     // be filled in on all the Lines (there will be some new Lines added to pLines too).
  83.     // Now just store them.
  84.     pRootNode = GenerateSubTree( pLines );
  85.     PrecalculateData( pLines );
  86.  
  87.     
  88.     puts("Checking BSP tree integrity ... ");
  89.         if( !CheckTreeValidity() )
  90.             puts("Check failed!\n");
  91.         else
  92.             puts("Check passed!\n");
  93.  
  94.     // Write the data to the output file.
  95.     printf("Writing data to %s.\n", pCommandLine->pOutputFile);
  96.     OutputTextData( pRootNode, pCommandLine->pOutputFile, pLines, pPoints );
  97.     
  98.     
  99.     // If there's an extra argument, graphically display the data.
  100. #ifdef DISPLAY_GRAPHICAL    
  101.     if( pCommandLine->bGraphicalDisplay )
  102.     {
  103.         printf("Displaying graphics...");
  104.         DisplayGraphicalData(pLines, pPoints);
  105.     }
  106. #endif
  107.     
  108.     printf("\nDone!\n\n");
  109.     return pRootNode;
  110. }
  111.  
  112.  
  113. CLine *GenerateSubTree( CLineArray *pTreeLines )
  114. {
  115.     CLineArray pLeftSide, pRightSide;
  116.     CLine   *pRootLine;
  117.     
  118.     // The terminal condition..
  119.     if( pTreeLines->NumElements() == 0 )
  120.         return NULL;
  121.     else if( pTreeLines->NumElements() == 1 )
  122.         return pTreeLines->GetLine(0);
  123.  
  124.     // Split the tree.
  125.     pRootLine = Split_Tree( pTreeLines, &pLeftSide, &pRightSide );
  126.  
  127.     pRootLine->pLeft = GenerateSubTree( &pLeftSide );
  128.     pRootLine->pRight = GenerateSubTree( &pRightSide );
  129.  
  130.     return pRootLine;
  131. }
  132.  
  133.  
  134. CLine *Split_Tree( CLineArray *pLineList, CLineArray *pLeftList, CLineArray *pRightList )
  135. {
  136.     CLine *pSplit;
  137.     
  138.     // These two are only used if a Line is split.
  139.     CLine *pNewLeft, *pNewRight;
  140.     
  141.     CLine   *pCurLine;
  142.     Index   curLine;
  143.  
  144.     SideDir testSide;
  145.     WORD    nElements;
  146.  
  147.     WORD nLeft, nRight, nSplit;
  148.     WORD curLeft=0, curRight=0, curSplit=0;
  149.  
  150.     // Just update this global variable.
  151.     ++nSplitTrees;
  152.  
  153.     // Get the best split out of the array.
  154.     pSplit = BestSplit( pLineList, &nLeft, &nRight, &nSplit );
  155.     
  156.     // Set the sizes of the arrays ahead of time instead of appending every line to save MUCH time.
  157.     pLeftList->SetSize( (UWORD)(nLeft+nSplit) );
  158.     pRightList->SetSize( (UWORD)(nRight+nSplit) );
  159.     
  160.     // Use a variable for the for loop because pLineList might get some elements added to it.
  161.     nElements = pLineList->NumElements();
  162.     for( curLine=0; curLine < nElements; curLine++ )
  163.     {
  164.         pCurLine = pLineList->GetLine(curLine);
  165.         
  166.         // Don't do anything to the Line you split everything by.
  167.         if( pCurLine == pSplit )
  168.             continue;           
  169.     
  170.         // See which side this Line is on.
  171.         testSide = LineSide( pSplit, pCurLine );
  172.  
  173.         switch( testSide )
  174.         {
  175.             case LeftSide:
  176.                 pLeftList->Set( curLeft, pCurLine );
  177.                 ++curLeft;
  178.                 break;
  179.             
  180.             case RightSide:
  181.                 pRightList->Set( curRight, pCurLine );
  182.                 ++curRight;
  183.                 break;
  184.             
  185.             case Intersect:
  186.                 ++nSplits;
  187.  
  188.                 SplitLine( pSplit, pCurLine, &pNewLeft, &pNewRight );
  189.                 
  190.                 pLeftList->Set( curLeft, pNewLeft );
  191.                 pRightList->Set( curRight, pNewRight );
  192.                 
  193.                 ++curLeft;
  194.                 ++curRight;
  195.                 break;
  196.         }
  197.     }
  198.     
  199.     return pSplit;
  200. }
  201.  
  202.  
  203. CLine *BestSplit( CLineArray *pLineList, WORD *pNLeft, WORD *pNRight, WORD *pNSplits )
  204. {
  205.      WORD curSplitLine, curLine;    
  206.     // The two types of tests that can be done.
  207.     // After finding the best of each, it makes a decision based on 
  208.     // the importance of having each type.
  209.     WORD bestNumSplits=32000, bestSplitIndex=0;
  210.     WORD bestBalance=32000, bestBalanceIndex=0;
  211.     
  212.     WORD nTestSplits, nLeft, nRight;
  213.     WORD bestLeft, bestRight, bestSplit;
  214.     WORD LeftRightDiff;
  215.  
  216.     CLine *pCurLine;
  217.     SideDir testSide;
  218.  
  219.  
  220.     // This starts numTestLines with a high value and brings it down gradually.
  221.     // It's very important that near the root node the tree is very balanced.  
  222.     // This ensures that it is.
  223.     WORD numTestLines = (WORD)(35 - nSplitTrees);
  224.  
  225.     if( numTestLines < 7 )
  226.         numTestLines = 7;
  227.  
  228.     if( numTestLines > pLineList->NumElements() )
  229.         numTestLines = pLineList->NumElements();
  230.  
  231.     // Tells if it's looking for the best balance or the least splits.
  232.     BOOL bGoForBalance;
  233.     
  234.  
  235.     if( forceBalance > 0 )
  236.     {
  237.         bGoForBalance = TRUE;
  238.         ++nBalancesChosen;
  239.  
  240.         --forceBalance;
  241.     }
  242.     else
  243.     {
  244. // ERASE THIS.
  245. hello = FDiv(FIX(nSplitsChosen), FIX(nBalancesChosen));
  246.         if( FDiv(FIX(nSplitsChosen), FIX(nBalancesChosen)) < (FIXED_ONE - balanceImportance) )
  247.         {
  248.             bGoForBalance = FALSE;
  249.             ++nSplitsChosen;
  250.         }
  251.         else
  252.         {
  253.             bGoForBalance = TRUE;
  254.             ++nBalancesChosen;
  255.         }
  256.     }
  257.     
  258.  
  259.  
  260.     for( curSplitLine=0; curSplitLine < numTestLines; curSplitLine++ )
  261.     {
  262.         pCurLine = pLineList->GetLine(curSplitLine);
  263.         nTestSplits=nLeft=nRight=0;
  264.  
  265.         for( curLine=0; curLine < pLineList->NumElements(); curLine++ )
  266.         {
  267.             // Test every Line in the array for the number of splits.
  268.             if( curLine == curSplitLine )
  269.                 continue;
  270.             
  271.             testSide = LineSide( pCurLine, pLineList->GetLine(curLine) );
  272.  
  273.             switch( testSide )
  274.             {
  275.                 case LeftSide:
  276.                     ++nLeft;
  277.                     break;
  278.  
  279.                 case RightSide:
  280.                     ++nRight;
  281.                     break;
  282.  
  283.                 case Intersect:
  284.                     ++nTestSplits;
  285.                     break;
  286.             }
  287.     
  288.         }
  289.                     
  290.  
  291.         if( bGoForBalance )
  292.         {
  293.                LeftRightDiff = (WORD)DIFF(nLeft,nRight);
  294.                
  295.                // Only do the best balance.
  296.                if( LeftRightDiff < bestBalance )
  297.                {
  298.                    bestBalance = LeftRightDiff;
  299.                 bestNumSplits = nTestSplits;
  300.  
  301.                 bestBalanceIndex = curSplitLine;
  302.             
  303.                    bestLeft = nLeft;
  304.                 bestRight = nRight;
  305.                 bestSplit = nTestSplits;
  306.                }
  307.                // This is an extra test here.  If the balances are the same, it gets the one
  308.             // with the least number of splits too.
  309.                else if( LeftRightDiff == bestBalance )
  310.             {
  311.                 if( nTestSplits < bestNumSplits )
  312.                 {
  313.                     bestBalanceIndex = curSplitLine;
  314.                     bestNumSplits = nTestSplits;
  315.             
  316.                        bestLeft = nLeft;
  317.                     bestRight = nRight;
  318.                     bestSplit = nTestSplits;
  319.                 }
  320.             }
  321.         }
  322.         else
  323.         {
  324.                // Only do the least number of splits.
  325.                if( nTestSplits < bestNumSplits )
  326.                {
  327.                 bestNumSplits = nTestSplits;
  328.                    bestSplitIndex = curSplitLine;
  329.                 
  330.                    bestLeft = nLeft;
  331.                 bestRight = nRight;
  332.                 bestSplit = nTestSplits;
  333.                }
  334.         }
  335.     }
  336.  
  337.  
  338.     *pNLeft = bestLeft;
  339.     *pNRight = bestRight;
  340.     *pNSplits = bestSplit;
  341.     
  342.  
  343.     if( bGoForBalance )
  344.         return pLineList->GetLine(bestBalanceIndex);
  345.     else
  346.         return pLineList->GetLine(bestSplitIndex);
  347. }
  348.  
  349.  
  350. SideDir LineSide( CLine *pMainLine, CLine *pTestLine )
  351. {
  352.     // Get the angle for pMainLine.
  353.     // Rotate both the Lines by pMainLine's angle.
  354.     // Parametrically clip pToSplit against the X axis.
  355.  
  356.     Angle angMain;
  357.     Fixed y1, y2, mainY;
  358.  
  359.     BOOL bSharePoint=FALSE;
  360.     WORD testSharePoint;
  361.     
  362.  
  363.     if( pMainLine->pPoint1 == pTestLine->pPoint1 || pMainLine->pPoint2 == pTestLine->pPoint1 )
  364.     {
  365.         bSharePoint = TRUE;
  366.         testSharePoint = 1;
  367.     }
  368.     else if( pMainLine->pPoint1 == pTestLine->pPoint2 || pMainLine->pPoint2 == pTestLine->pPoint2 )
  369.     {
  370.         bSharePoint = TRUE;
  371.         testSharePoint = 2;
  372.     }
  373.         
  374.     
  375.     angMain = GetAngle( pMainLine->pPoint1->localX, pMainLine->pPoint1->localY,
  376.                         pMainLine->pPoint2->localX, pMainLine->pPoint2->localY );
  377.     
  378.     angMain = (ANGLE_RES - angMain) & ANGLE_MASK;
  379.     
  380.     // Rotate all of pToSplit's vertices *around* pMainLine's first Point.
  381.     RotatePointYOnly( pMainLine->pPoint1->localX, pMainLine->pPoint1->localY,
  382.                 angMain, pTestLine->pPoint1->localX, pTestLine->pPoint1->localY,
  383.                 &y1 );
  384.  
  385.     RotatePointYOnly( pMainLine->pPoint1->localX, pMainLine->pPoint1->localY,
  386.                 angMain, pTestLine->pPoint2->localX, pTestLine->pPoint2->localY,
  387.                 &y2 );
  388.  
  389.  
  390.     mainY = FIX(pMainLine->pPoint1->localY);
  391.  
  392.     if( bSharePoint )
  393.     {
  394.         if( testSharePoint == 1 )
  395.         {
  396.             if( y2 < mainY )
  397.                 return RightSide;
  398.             else if( y2 > mainY )
  399.                 return LeftSide;
  400.             else
  401.                 return Intersect;
  402.         }
  403.         else
  404.         {
  405.             if( y1 < mainY )
  406.                 return RightSide;
  407.             else if( y1 > mainY )
  408.                 return LeftSide;
  409.             else
  410.                 return Intersect;        
  411.         }
  412.     }
  413.  
  414.     
  415.     if( y1 < mainY && y2 < mainY )
  416.         return RightSide;
  417.     else if( y1 > mainY && y2 > mainY )
  418.         return LeftSide;
  419.     
  420.     else if( y1 == mainY && y2 < mainY )
  421.         return RightSide;
  422.     else if( y2 == mainY && y1 < mainY )
  423.         return RightSide;
  424.     
  425.     else if( y1 == mainY && y2 > mainY )
  426.         return LeftSide;
  427.     else if( y2 == mainY && y1 > mainY )
  428.         return LeftSide;
  429.  
  430.     else
  431.         return Intersect;
  432. }
  433.  
  434.  
  435. BOOL SplitLine( CLine *pMainLine, CLine *pToSplit, CLine **pNewLeft, CLine **pNewRight )
  436. {
  437.     // Get the angle for pMainLine.
  438.     // Rotate both the Lines by pMainLine's angle.
  439.     // Parametrically clip pToSplit against the X axis.
  440.  
  441.     Angle angMain;
  442.  
  443.     Fixed x1, y1, x2, y2;
  444.     Fixed t, newX, newY;
  445.  
  446.     CPoint  *pNewPoint;
  447.     CLine   *pNewLine;
  448.  
  449.     // The side of pMainLine that pToSplit ends up on.
  450.     SideDir splitSide;
  451.  
  452.  
  453.     angMain = GetAngle( pMainLine->pPoint1->localX, pMainLine->pPoint1->localY,
  454.                         pMainLine->pPoint2->localX, pMainLine->pPoint2->localY );
  455.  
  456.     angMain = (ANGLE_RES - angMain) & ANGLE_MASK;
  457.     
  458.     // Rotate all of pToSplit's vertices *around* pMainLine's first Point.
  459.     RotatePointYOnly( pMainLine->pPoint1->localX, pMainLine->pPoint1->localY,
  460.                 angMain, pToSplit->pPoint1->localX, pToSplit->pPoint1->localY,
  461.                 &y1 );
  462.  
  463.     RotatePointYOnly( pMainLine->pPoint1->localX, pMainLine->pPoint1->localY,
  464.                 angMain, pToSplit->pPoint2->localX, pToSplit->pPoint2->localY,
  465.                 &y2 );
  466.  
  467.     
  468.     // Test for the special case here, where pToSplit lies exactly on pMainLine.
  469.     // In this case, a completely different action is taken.  This needs to be before
  470.     // you get t, because you'll get a divide by zero error if this isn't handled.
  471.     if( y1 == FIX(pMainLine->pPoint1->localY) && y2 == FIX(pMainLine->pPoint1->localY) )
  472.     {
  473.         ++nExactIntersections;
  474.         
  475.         pNewLine = new CLine;
  476.         pLines->Append( pNewLine );
  477.         
  478.         memcpy( pNewLine, pToSplit, sizeof(CLine) );
  479.  
  480.         // Switch their directions.
  481.         pNewLine->pPoint2 = pToSplit->pPoint1;
  482.         pNewLine->pPoint1 = pToSplit->pPoint2;
  483.         
  484. // TODO:  You might need to assign the new Line to a different side...
  485.         // Make sure the Lines are on the right sides of the partition and give them
  486.         // their correct textures.
  487.         *pNewLeft = pNewLine;
  488.         *pNewRight = pToSplit;
  489.  
  490.         pNewLine->wallColor = pToSplit->wallColor;
  491.         pNewLine->idRightTex = pToSplit->idLeftTex;
  492.         pNewLine->idLeftTex = BAD_TEXTURE_ID;
  493.         pToSplit->idLeftTex = BAD_TEXTURE_ID;
  494.         
  495.         return TRUE;
  496.     }
  497.  
  498.     
  499.     // Find where they intersect the Y axis of pMainLine's pPoint1.
  500.     t = FDiv( (FIX(pMainLine->pPoint1->localY) - y1), (y2-y1) );
  501.     
  502.     // Find out which side each new line will be on.
  503.     if( y1 <= FIX(pMainLine->pPoint1->localY) )
  504.         splitSide = RightSide;
  505.     else
  506.         splitSide = LeftSide;
  507.  
  508.  
  509.     // Now get where the new Point should be.
  510.     x1 = FIX(pToSplit->pPoint1->localX);
  511.     y1 = FIX(pToSplit->pPoint1->localY);
  512.     x2 = FIX(pToSplit->pPoint2->localX);
  513.     y2 = FIX(pToSplit->pPoint2->localY);
  514.  
  515.     newX = x1 + FMul( t, (x2-x1) );
  516.     newY = y1 + FMul( t, (y2-y1) );
  517.  
  518.     // Create the new Point and Line and fill in their stuff.
  519.     pNewPoint = new CPoint;
  520.     pPoints->Append(pNewPoint);
  521.     
  522.     pNewLine = new CLine;   
  523.     memset( pNewLine, 0, sizeof(CLine) );
  524.     pLines->Append(pNewLine);
  525.     
  526.     pNewPoint->localX = (WORD)UNFIX(newX);
  527.     pNewPoint->localY = (WORD)UNFIX(newY);
  528.     
  529.  
  530.     pNewLine->pPoint1 = pNewPoint;
  531.     pNewLine->pPoint2 = pToSplit->pPoint2;
  532.     pToSplit->pPoint2 = pNewPoint;
  533.  
  534.     pNewLine->wallColor = pToSplit->wallColor;
  535.     pNewLine->idLeftTex = pToSplit->idLeftTex;
  536.     pNewLine->idRightTex = pToSplit->idRightTex;
  537.  
  538.     // Fill in the return information.
  539.     if( splitSide == LeftSide )
  540.     {
  541.         *pNewLeft = pToSplit;
  542.         *pNewRight = pNewLine;
  543.     }
  544.     else
  545.     {
  546.         *pNewLeft = pNewLine;
  547.         *pNewRight = pToSplit;
  548.     }
  549.  
  550.     return TRUE;
  551. }
  552.  
  553.  
  554. Angle DirectionDiff( Angle compass1, Angle compass2, SideDir diffDir )
  555. {
  556.     Angle translatedCompass2;
  557.     
  558.     // Put compass1 at 0 and translate compass2 by that amount.
  559.     translatedCompass2 = (Angle)((compass2 - compass1) & ANGLE_MASK);
  560.  
  561.     if( diffDir == LeftSide )
  562.         return translatedCompass2;
  563.     else
  564.         return (Angle)(ANGLE_RES - translatedCompass2);
  565. }
  566.  
  567.  
  568. BOOL PrecalculateData( CLineArray *pLineList )
  569. {
  570.     WORD i;
  571.     CLine *pCurLine;
  572.     WORD lineLength;
  573.     
  574.     for( i=0; i < pLineList->NumElements(); i++ )
  575.     {
  576.         pCurLine = pLineList->GetLine(i);
  577.         
  578.         // Do the texture mapping placement
  579.         pCurLine->texOriginX = pCurLine->pPoint1->localX;
  580.         pCurLine->texOriginY = pCurLine->pPoint1->localY;
  581.         
  582.         pCurLine->lineAngle = GetAngle( pCurLine->pPoint1->localX, pCurLine->pPoint1->localY, pCurLine->pPoint2->localX, pCurLine->pPoint2->localY );
  583.         pCurLine->SetTextureXLength( 64 );
  584.  
  585.         // Fill in the coefficients of the Line's plane equation.
  586.         pCurLine->A = pCurLine->pPoint1->localY - pCurLine->pPoint2->localY;
  587.         pCurLine->B = pCurLine->pPoint2->localX - pCurLine->pPoint1->localX;
  588.         pCurLine->C = -((pCurLine->A * pCurLine->pPoint1->localX) + (pCurLine->B * pCurLine->pPoint1->localY));
  589.  
  590.         // Normalize A, B, and C.
  591.         lineLength = sqrt( SQR(pCurLine->pPoint2->localX - pCurLine->pPoint1->localX) + SQR(pCurLine->pPoint2->localY - pCurLine->pPoint1->localY) );
  592.         if( lineLength == 0 )
  593.             lineLength = 1;
  594.             
  595.         pCurLine->A = FIX(pCurLine->A) / lineLength;
  596.         pCurLine->B = FIX(pCurLine->B) / lineLength;
  597.         pCurLine->C = FIX(pCurLine->C) / lineLength;
  598.     }
  599.  
  600.     
  601.     return TRUE;
  602. }
  603.  
  604.  
  605. BOOL CheckTreeValidity()
  606. {
  607.     WORD i, j;
  608.     CLine *pMain, *pTest;
  609.  
  610.     for( i=0; i < pLines->NumElements(); i++ )
  611.     {
  612.         pMain = pLines->GetLine(i);
  613.         
  614.         if( pMain->pLeft == NULL && pMain->pRight == NULL )
  615.             continue;
  616.             
  617.         for( j=0; j < pLines->NumElements(); j++ )
  618.         {
  619.             if( i == j )
  620.                 continue;
  621.             
  622.             pTest = pLines->GetLine(j);
  623.  
  624.             if( pMain->pLeft == pTest->pLeft )
  625.                 if( pMain->pLeft != NULL )
  626.                     return FALSE;
  627.  
  628.             if( pMain->pRight == pTest->pRight )
  629.                 if( pMain->pRight != NULL )
  630.                     return FALSE;
  631.  
  632.             if( pMain->pLeft == pTest->pRight )
  633.                 if( pMain->pLeft != NULL )
  634.                     return FALSE;
  635.  
  636.             if( pMain->pRight == pTest->pLeft )
  637.                 if( pMain->pRight != NULL )
  638.                     return FALSE;
  639.         }    
  640.     }
  641.  
  642.     return TRUE;
  643. }
  644.  
  645.  
  646.